%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}
%\usecolortheme{orange}
%\setbeamercolor{palette primary}{fg=white,bg=orange} % changed this
%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

\setbeamertemplate{navigation symbols}{} % To remove the navigation symbols from the bottom of all slides uncomment this line
}

\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Truncated Multipliers]{Fixed-Width Truncated Multipliers} % The short title appears at the bottom of every slide, the full title is only on the title page
\subtitle{Survey, Implementation and Proposal}
\author{Tuan Nguyen} % Your name
\institute[ECE] % Your institution as it will appear on the bottom of every slide, may be shorthand to save space
{
Oklahoma State University \\ % Your institution for the title page
\medskip
\textit{tuan.d.nguyen@okstate.edu} % Your email address
}
\date{\today} % Date, can be changed to a custom date

\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Outline} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------

%------------------------------------------------
\section{Introduction} % Sections can be created in order to organize your presentation into discrete blocks, all sections and subsections are automatically printed in the table of contents as an overview of the talk
%------------------------------------------------
\subsection{Fixed-Width Multipliers} % A subsection can be created just before a set of slides with a common theme to further break down your presentation into chunks
%------------------------------------------------
\begin{frame}

\frametitle{Introduction}
\begin{columns}[c]
\column{0.4\textwidth}
\begin{figure}
\includegraphics[scale=0.7]{imgs/fw_overview.pdf} 
\caption{$n$ bits Fixed-Width Multipliers}
\end{figure}
\column{0.6\textwidth}
Fixed-Width Multipliers
\begin{itemize}
\item Fundamental block in many DSP Systems\footnotemark
\item All multiplicand, multiplier and product are $n$-bits binary numbers
\item Avoid grown in word size
\end{itemize}
\end{columns}
\footnotetext{\begin{tiny}Ma, G-K., and Fred J. Taylor. "Multiplier policies for digital signal processing." ASSP Magazine, IEEE 7.1 (1990): 6-20.\end{tiny}}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Fixed-Width Non-Truncated Multipliers}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/full_width.pdf}
\caption{Non-Truncated Multipliers}
\end{figure}
\column{0.5\textwidth}
\begin{itemize}
\item Compute full-width product (2n-bits)$Z$
\item Round $2n$-bits $Z$ product to $n$-bit final product $\hat{Z}$
\item Error = Rounding Error
 \[
 E_{rnd} = \hat{Z} - Z
 \]
\end{itemize}
%Advantages:
%\begin{itemize}
%\item Smallest error
%\end{itemize}
%Disadvantages:
%\begin{itemize}
%\item Must compute $n^2$ partial products and then sum of them
%\item Worst in terms of area, delay, power dissipation
%\end{itemize}

\end{columns}
\end{frame}
%------------------------------------------------
\subsection{Fixed-Width Truncated Multipliers}
%------------------------------------------------
\begin{frame}
\frametitle{Fixed-Width Truncated Multipliers}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/trunc_mult_overview.pdf} 
\caption{$NxN$ Truncated Multipliers}
\end{figure}

\column{0.5\textwidth}
\begin{itemize}
\item $(n-k)$ least significant columns truncated $(k << n)$
\item \emph{Correction Value} $C$ added to $(n+k)$ remained columns to form estimation $Z_{est}$
\item $Z_{est}$ rounded to $n$ bits final product $\hat{Z}$
\item Error = Reduction Error + Rounding Error
\end{itemize}
\end{columns}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Truncated vs. Non-Truncated}
%\begin{itemize}
%\item Proposed in Lim's landmark paper(1992) \cite{lim:1992}
%\item In comparison with Non-Truncated Multipliers
%\begin{itemize}
%\item Save up to $20\% - 40\%$ area 
%\item Save up to $20\% - 50\%$ power dissipation 
%\end{itemize}
%\item There are two sources of errors:
%\begin{itemize}
%\item Reduction Error due to truncation
%\item Rounding Error due to rounding
%\end{itemize}
%\item \emph{Correction Value} $C$ is to compensate for errors due to truncation and rounding
\begin{small}
\begin{columns}[T]
\column{0.5\textwidth}
\begin{itemize}
\item Error = Reduction Error + Rounding Error $\rightarrow$ Larger Error
\item Compute then sum just $M = N^2 - \frac{(N-k)*(N-k+1)}{2}$ PPs
\item \textbf{Better in terms of area, delay and power dissipation}
\end{itemize}
\column{0.5\textwidth}
\begin{itemize}
\item Error = Rounding Error $\rightarrow$ Smallest error
\item Compute then sum all $N^2$ PPs
\item Worst in terms of area, delay and power dissipation
\end{itemize}

\end{columns}
\end{small}

%\end{itemize}

$\rightarrow$ Various methods were proposed to find Correction Value $C$ to improve the errors of Truncated Multipliers
\end{frame}
%------------------------------------------------
\section{State-of-the-Art}
%------------------------------------------------
\subsection{Constant Correction Truncation Methods}
%------------------------------------------------
\begin{frame}
\frametitle{State-of-the-Art}
\begin{enumerate}
\item Non-Truncated Multipliers
\item Constant Correction Truncation Methods:
\begin{enumerate}
\item Fixed-Bias Correction\cite{lim:1992}
\item Constant Correction Truncation\cite{schulte:1993}
\end{enumerate}
\item Variation Correction Truncation Methods:
\begin{enumerate}
\item Data-Dependent Truncation\cite{king:1997}
\item Hybrid Truncated Multipliers\cite{stine:2003}
\item Petra's Method\cite{petra:2010}
\end{enumerate}
\end{enumerate}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Notation}
Multiplicand $A$ and Multiplier $B$($n$ bits unsigned binary numbers):
\[
A = \sum_{i=1}^{n}{a_i \cdot 2^{-i}} \hspace{1 cm} B = \sum_{j=1}^{n}{b_j \cdot 2^{-j}}
\]
The True Product $Z$ ($2n$ bits):
\[
Z = A \cdot B = \sum_{i=1}^{n}\sum_{j=1}^{n} (a_i \cdot b_j) \cdot 2 ^{-i-j} =  \sum_{k=1}^{2n} {\pi_k \cdot 2^{-k}}
\]
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Non-Truncated Multipliers}
\begin{columns}[c]
\column{0.6\textwidth}
Round $Z$ to $n$ bits final product $\hat{Z}$:
\[
\hat{Z} = \frac{\left[ Z \cdot 2^n \right]}{2^n}
\]

The error is the rounding error:
\[
E = E_{rnd} = \hat{Z} - Z =  \frac{\left[ Z \cdot 2^n \right]}{2^n} - Z
\]
\[
\rightarrow \left|E \right| \le \frac{0.5}{2^n} = 0.5ulp
\]
%and 
%\[
%E_{avg} = 0
%\]
\column{0.4\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/full_width.pdf}
\caption{NxN Non-Truncated Multipliers}
\end{figure}
\end{columns}
%\footnotetext{$[X]$ is the round to nearest integer function}
%\footnotetext{$ulp$ is unit at last place ($=2^{-n}$ in $n$ bits unsigned binary number)}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Truncated Multipliers}
\begin{columns}[c]
\column{0.6\textwidth}
Only $(n+k-1)$ most significant columns used:
\[
Z_{trunc} =  \sum_{i=1,j=1}^{i+j \le n+k}(a_i \cdot b_j) \cdot 2 ^{-i-j}
\]
Correction Value $C$ added to form estimation product $Z_{est}$:
\[
{Z}_{est} = Z_{trunc} + C
\]
$Z_{est}$ then rounded to have the $n$ bits final product $\hat{Z}$
\[
\hat{Z}_{trunc} = \frac{\left[(Z_{est})\cdot 2^n \right]}{2^n}
\]
\column{0.4\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/trunc_mult_overview.pdf} 
\caption{$NxN$ Truncated Multipliers}
\end{figure}
\end{columns}
%\footnotetext{column $m$ is the set of all PPs $a_i \cdot b_j$ such that $i+j = m$}
\end{frame}
%------------------------------------------------
%------------------------------------------------
\begin{frame}
\frametitle{Truncated Multipliers (cont.)}
\begin{columns}[c]
\column{0.6\textwidth}
Constant Correction Methods:
\begin{itemize}
\item Correction Value $C$ is constant
\item Fixed-Bias Correction (Lim,1992) and Constant Correction Truncation (Schulte,1993)
\end{itemize}
Variation Correction Methods:
\begin{itemize}
\item $C$ is input-dependent (function of inputs)
\item Data-Dependent Truncation (King,1997), Hybrid Truncated Multipliers (Stine,2003), Petra Method(Petra, 2010)
\end{itemize}
\column{0.4\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/trunc_mult_overview.pdf} 
\caption{$NxN$ Truncated Multipliers}
\end{figure}
\end{columns}
%\footnotetext{column $m$ is the set of all PPs $a_i \cdot b_j$ such that $i+j = m$}
\end{frame}
%------------------------------------------------
%\begin{frame}
%\frametitle{Error Analysis}
%The total errors of Truncated Fixed-Width Multipliers come from two operations: reduction and rounding:
%\[
%E_{total} = E_{red} + E_{rnd} = \hat{Z}_{trunc} - Z
%\]
%The reduction error $E_{red}$ due to truncation is:
%\[
%E_{red} = Z_{est} - Z = (Z_{trunc} + C) - Z
%\]
%The rounding error $E_{rnd}$ due to rounding is:
%\[
%E_{rnd} = \hat{Z}_{trunc} - Z_{est} = \frac{\left[(Z_{est})\cdot 2^n \right]}{2^n} - Z_{est}
%\]
%\end{frame}
%------------------------------------------------
%\begin{frame}
%\frametitle{Non-Correction Truncation Method}
%\begin{columns}[c]
%\column{0.6\textwidth}
%\begin{itemize}
%\item $C = 0$ for every inputs $\rightarrow Z_{est} = Z_{trunc}$
%\item Final Product $\hat{Z}_0 = \frac{\left[(Z_{trunc})\cdot 2^n \right]}{2^n}$
%\item Simplest, best in terms of area, delay and power dissipation
%\item Worst in term of errors
%\end{itemize}
%\column{0.4\textwidth}
%\begin{figure}
%\includegraphics[width=\columnwidth]{imgs/non_truncation.pdf} 
%\caption{$NxN$ Truncated Multipliers}
%\end{figure}
%\end{columns}
%\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Fixed-Bias Correction\footnotemark[2]}
\begin{columns}[c]
\column{0.6\textwidth}
\begin{itemize}
\item Basic idea: find Correction Value by analyzing errors statistically
\item Assumptions:
\begin{itemize}
\item Each of PPs $a_i\cdot b_j$ is regarded as a random variable with identical independent distribution (i.i.d)
\item Probability of $a_i$ or $b_j$ having value 1 is assumed $\frac{1}{2}$
\end{itemize}
\item Probability of each PPs $a_i \cdot b_j$ having the value 1 is $\frac{1}{4}$ $\rightarrow$ Expected value of each PPs $a_i \cdot b_j$ is $\frac{1}{4}$
\end{itemize}

\column{0.4\textwidth}
\begin{figure}
\includegraphics[width=\columnwidth]{imgs/Lim.pdf} 
\caption{Lim's Method}
\end{figure}
\end{columns}
\footnotetext[2]{\begin{tiny}Lim, Y. C. "Single-precision multiplier with reduced circuit complexity for signal processing applications." Computers, IEEE Transactions on 41.10 (1992): 1333-1336.\end{tiny}}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Fixed-Bias Correction}
The Correction Value is now chosen as the expected value of the truncated part as following:
\begin{columns}[c]
\column{0.5\textwidth}
\begin{align*}
C_L   &= E \left\lbrace Z - Z_{trunc} \right\rbrace\\
	&= E \left\lbrace  \sum^{n+k<i+j\le 2n} {(a_i\cdot b_j) 2^{-i-j}} \right\rbrace \\
   &= \frac{1}{4} \sum_{m=n+k+1}^{2n} (2n+1-m) 2^{-m}\\
\end{align*}
\column{0.5\textwidth}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=1]{imgs/Lim.pdf}
\caption{Lim's Method}
\end{figure}
\end{columns}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Constant Correction Truncation\footnotemark[3]}
\begin{columns}[c]
\column{0.4\textwidth}
\begin{figure}[hbtp]
\centering
\includegraphics[width=\linewidth]{imgs/schulte.pdf}
\caption{Schulte's Method}
\end{figure}
\column{0.6\textwidth}
\begin{small}
\begin{itemize}
\item Reduction Error: still use $C_L$
\item Rounding Error:
\begin{itemize}
\item Each $\pi_t (n<t\le n+k)$ is i.i.d random variable and $P(\pi_t=0) = P(\pi_t=1) = 0.5$
\item Expected value of rounded part:
\[
\mathbf{E}(rounded) = (2^k - 1) \cdot 2^{-n-k-1}
\]
\end{itemize}
\item CCT Correction Value $C_S$ is
\[
C_{S} = C_L + (2^k - 1) \cdot 2^{-n-k-1}
\]
\item Round $C_S$ to $(n+k)$ bits $\hat{C}_S$
\[
\hat{C}_{S} = \frac{\left[C_{S} \cdot 2^{n+k}\right]}{2^{n+k}}
\]
\end{itemize}
\end{small}
\end{columns}
%Assumption:
%$\pi_t$ of $Z_{trunc}$, with $(n+1\le t \le n+k)$ (rounded bits), is independent random variable and the probability of $\pi_t$ having value 1 is 1/2
\footnotetext[3]{\begin{tiny}Schulte, Michael J., and Earl E. Swartzlander. "Truncated multiplication with correction constant [for DSP]." VLSI Signal Processing, VI, 1993.,[Workshop on]. IEEE, 1993.\end{tiny}}
\end{frame}

%------------------------------------------------
\subsection{Variation Correction Truncation Methods}
%------------------------------------------------

\begin{frame}
\frametitle{Data-Dependent Truncation\footnotemark[4]}
\begin{columns}[c]
\column{0.4\textwidth}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=1.2]{imgs/king.pdf}
\caption{Data-Dependent Truncation}
\end{figure}

\column{0.6\textwidth}
\begin{itemize}
\item Count $N1=$ number of ONE in column $(n+k+1)$ 
\item Add $N1$ to column $(n+k)$
\item Same rounding error as Schulte's method
\item Correction Value $C_K$
\[
C_{K} = N1\cdot 2^{-n-k} + (2^k - 1) \cdot 2^{-n-k-1}
\]
\item Round $C_K$ to $\hat{C}_K$
\[
\hat{C}_{K} = \frac{\left[C_{K} \cdot 2^{n+k}\right]}{2^{n+k}}
\]
\end{itemize}
\end{columns}
\footnotetext[4]{\begin{tiny}King, Eric J., and E. E. Swartzlander. "Data-dependent truncation scheme for parallel multipliers." Signals, Systems Computers, 1997. Conference Record of the Thirty-First Asilomar Conference on. Vol. 2. IEEE, 1997. \end{tiny}}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Hybrid Truncated Multipliers\footnotemark[5]}
\begin{columns}[c]
\column{0.4\textwidth}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=1.2]{imgs/stine.pdf}
\caption{Hybrid Truncated Multipliers}
\end{figure}
\column{0.6\textwidth}
\begin{small}

\begin{itemize}
\item Combine both CCT method and DDT method 
\item Introduce parameter $p$ to adjust the percentage of column $(n+k+1)$
\[
N1_{H} = \left\lfloor( N1 \cdot p )\right\rfloor
\]
\item The HCT Correction Value $C_H$:
\[
C_{H} = C_S - N1_H \cdot 2^{-n-k}
\]
\item Round $C_H$ to $(n+k)$ bits $\hat{C}_H$
\[
\hat{C}_{H} = \frac{\left[C_{H} \cdot 2^{n+k}\right]}{2^{n+k}}
\]
\end{itemize}
\end{small}
\end{columns}
\footnotetext[5]{\begin{tiny}Stine, James E., and Oliver M. Duverne. "Variations on truncated multiplication." Digital System Design, 2003. Proceedings. Euromicro Symposium on. IEEE, 2003. \end{tiny}}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Petra Method\footnotemark[6]}
\begin{columns}[c]
\column{0.4\textwidth}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=1.2]{imgs/petra.pdf}
\caption{Petra Method}
\end{figure}
\column{0.6\textwidth}
\begin{small}

\begin{itemize}
\item Assume Uniform Distribution of inputs to simplify error estimation
\item  Variable Correction Truncation:
\[
C_P = f(IC) 
\]
\item Simplify $f(IC)$ to a linear combination of bits in $IC$
\item Optimize Mean Square Error 
\end{itemize}
\end{small}
\end{columns}
\footnotetext[6]{\begin{tiny}Petra, Nicola, et al. "Truncated binary multipliers with variable correction and minimum mean square error." Circuits and Systems I: Regular Papers, IEEE Transactions on 57.6 (2010): 1312-1325. \end{tiny}}
\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Compare and Contrast}
\begin{tiny}
\begin{table}[!t]
%\renewcommand{\arraystretch}{1.3}
\caption{Compare and Contrast}
\label{tb:compare}
\centering
\begin{tabular}{l||c|c|c|c}
\hline
\bfseries Methods & \bfseries Type & \bfseries Error Compensation &\bfseries Assumption &\bfseries Approach\\
\hline\hline
Fixed-Bias(Lim)\cite{lim:1992}& CCT &Reduction & Uniform Distribution & Heuristic\\
CCT(Schulte)\cite{schulte:1993}& CCT &Reduction + Rounding&  Uniform Distribution	& Heuristic	\\
Data-Dependent(King)\cite{king:1997}&VCT &Reduction +  Rounding	& Uniform Distribution	& Heuristic		 \\
Hybrid(Stine)\cite{stine:2003}&VCT &Reduction + Rounding	& Uniform Distribution	& Heuristic	 \\
Petra\cite{petra:2010}&VCT &Reduction + Rounding	& Uniform Distribution	& Optimization	 \\
\hline
\end{tabular}
\end{table}
\end{tiny}
\end{frame}

%------------------------------------------------



%------------------------------------------------
\section{Experimental Results}
%------------------------------------------------
\subsection{Error Measurement \& Analysis}
%------------------------------------------------

\begin{frame}
\frametitle{Experimental Results}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.8]{imgs/design_flow.pdf}
\caption{Design Flow}
\end{figure}
 
\end{frame}
%------------------------------------------------

%------------------------------------------------
\begin{frame}
\frametitle{Implementations\footnotemark[7]}
Error Measurement \& Analysis:
\begin{itemize}
\item Implemented in Matlab: NTM, Lim, Schulte, King, Stine methods
\item Measure Mean Absolute Error and Maximum Absolute Error
\end{itemize}
Area/Delay Measurement \& Analysis:
\begin{itemize}
\item Implemented in Verilog: NTM, Lim, Schulte, King, Stine methods
\item Synthesized on Xilinx Virtex 5 (xc5vtx240t) FPGA using Xilinx ISE
\item Measure Area and Delay
\end{itemize}
\footnotetext[7]{\begin{tiny}
T. Nguyen. Truncated Multipliers Version 1, 2014.
\end{tiny}}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{small}

\begin{table}[!t]
%\renewcommand{\arraystretch}{0.8}
\caption{Mean Absolute Error Measurement (ulp)}
\label{tb:mae}
\centering
\begin{tabular}{c||c|c|c|c|c}
\hline
\bfseries $(n,k)$ & \bfseries NTM &\bfseries Lim &\bfseries Schulte &\bfseries King &\bfseries Stine\\
\hline\hline

$(4,1) $& \textbf{0.2344}&		0.5352&	0.2686&	0.3125&	\textbf{0.2656}\\
$(4,2) $&\textbf{ 0.2344}&		0.2754&	0.2363&	0.2520&	\textbf{0.2441}\\
\hline
$(8,1) $& \textbf{0.2490}&		2.0001&	0.4134&	0.3497&	\textbf{0.3494}\\
$(8,2) $& \textbf{0.2490}&		0.5758&	0.2878&	0.2732&	\textbf{0.2727}\\
$(8,3) $& \textbf{0.2490}&		0.2598&	0.2590&	0.2547&	\textbf{0.2545}\\
\hline
$(12,1) $&\textbf{0.2499}&		3.5000&	0.5119&	0.3688&	\textbf{0.3403}\\
$(12,2) $&\textbf{0.2499}&		1.3126&	0.3254&	0.2794&	\textbf{0.2716}\\
$(12,3) $&\textbf{0.2499}&		0.3636&	0.2696&	0.2570&	\textbf{0.2550}\\
$(12,4) $&\textbf{0.2499}&		0.2731&	0.2536&	0.2516&	\textbf{0.2511}\\
\hline
\end{tabular}
\end{table}

\end{small}
%\begin{itemize}
%\item ac
%\item df
%\end{itemize}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{imgs/plot_mean.png}
\caption{Mean Absolute Error Measurement (ulp)}
\end{figure}
 \end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{small}

\begin{table}[!t]
%\renewcommand{\arraystretch}{1.3}
\caption{Maximum Absolute Error Measurement (ulp)}
\label{tb:mxe}
\centering
\begin{tabular}{c||c|c|c|c|c}
\hline
\bfseries $(n,k)$ & \bfseries NTM &\bfseries Lim &\bfseries Schulte &\bfseries King &\bfseries Stine\\
\hline\hline
$(4,1) $&0.5000		&1.0000	&1.0625	&\textbf{0.9375}	&\textbf{0.7500}\\
$(4,2) $&0.5000		&\textbf{0.8125}	&\textbf{0.5625}	&\textbf{0.6875}	&\textbf{0.6250}\\
$(8,1) $&0.5000		&3.0000	&2.5039	&1.2773	&1.1953\\
$(8,2) $&0.5000		&1.2500	&1.2539	&\textbf{0.8477}	&\textbf{0.8047}\\
$(8,3) $&0.5000 	&\textbf{0.8789}	&\textbf{0.7539}	&\textbf{0.6523}	&\textbf{0.6328}\\
$(12,1) $&0.5000        &5.0000    &4.0002    &1.6111    &1.4443 \\
$(12,2) $&0.5000        &2.2500    &2.0002    &1.0139    &\textbf{0.9307} \\
$(12,3) $&0.5000        &1.0000    &1.1252    &\textbf{0.7361}    &\textbf{0.6943} \\
$(12,4) $&0.5000		   &\textbf{0.9377}	  &\textbf{0.8127}	 &\textbf{0.6077}	&\textbf{0.5869} \\
\hline
\end{tabular}
\end{table}
\end{small}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{imgs/plot_max.png}
\caption{Mean Absolute Error Measurement (ulp)}
\end{figure}
 \end{frame}

%------------------------------------------------
\subsection{Area/Delay Measurement \& Analysis}
%------------------------------------------------
\begin{frame}
\frametitle{Area Measurement \& Analysis}
\begin{small}
\begin{table}[!t]
%\renewcommand{\arraystretch}{1.3}
\caption{Area Measurement (BLES)-Array}
\label{tb:area}
\centering
\begin{tabular}{c||c|c|c|c|c}
\hline
\bfseries $(n,k)$ & \bfseries NTM &\bfseries Lim &\bfseries Schulte &\bfseries King &\bfseries Stine\\
\hline\hline
$(4,1) $& 20&		12&	12&	\textbf{11}&	12\\
$(4,2) $& 20&		\textbf{14}&	\textbf{14}&	16&	\textbf{14}\\
$(8,1) $& 91&		53&	53&	\textbf{50}&	53 \\
$(8,2) $& 91&		\textbf{60}&	\textbf{60}&	62&	\textbf{60} \\
$(8,3) $& 91&		72&	72&	\textbf{66}&	72 \\
$(12,1) $&209&   118&118&\textbf{112}&118\\
$(12,2) $&209&   136&\textbf{131}&132 &\textbf{131} \\
$(12,3) $&209&	 143&143&\textbf{140} &143  \\
$(12,4) $&209&   164&160&\textbf{153} & 160\\
\hline
\end{tabular}
\end{table}
\end{small}
\end{frame}
%------------------------------------------------
%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{imgs/plot_area.png}
\caption{Area Measurement (BLES)-Array}
\end{figure}
 \end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Delay Measurement \& Analysis}
\begin{small}
\begin{table}[!t]
%\renewcommand{\arraystretch}{1.3}
\caption{Delay Measurement (ns)-Array}
\label{tb:delay}
\centering
\begin{tabular}{c||c|c|c|c|c}
\hline
\bfseries $(n,k)$ & \bfseries NTM &\bfseries Lim &\bfseries Schulte &\bfseries King &\bfseries Stine\\
\hline\hline
$(4,1) $& 6.283&		6.794&	6.794&	\textbf{6.153}&	6.794\\
$(4,2) $& \textbf{6.283}&		6.463&	6.463&	7.215&	6.463\\
$(8,1) $& 12.295&		\textbf{10.114}&	\textbf{10.114}&	11.854&	\textbf{10.114} \\
$(8,2) $& 12.295&		12.209&	12.214&	\textbf{12.200}&	12.214 \\
$(8,3) $& 12.295&		12.248&	\textbf{12.180}&	12.223&\textbf{12.180}	 \\
$(12,1) $&16.258&	 \textbf{14.513}&\textbf{ 14.513}& 15.798		&\textbf{14.513} \\
$(12,2) $&16.258& 	 16.438& 16.433&\textbf{16.143}	& 16.433\\
$(12,3) $&16.258&    16.388&16.388&\textbf{16.167}	&16.388\\
$(12,4) $&\textbf{16.258}& 	 16.753 &17.049&16.534		&17.049\\
\hline
\end{tabular}
\end{table}
\end{small}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Errors Measurement \& Analysis}
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{imgs/plot_delay.png}
\caption{Delay Measurement (ns)-Array}
\end{figure}
 \end{frame}

%------------------------------------------------
%------------------------------------------------
\section{Proposal}
%------------------------------------------------
\subsection*{Proposal}
%------------------------------------------------
\begin{frame}
\frametitle{Proposal}
\begin{block}{\textbf{Problems}}
As far as my knowledge, implicitly or explicitly, all Fixed-Width Truncated Multipliers so far assume that the \emph{probability of each input digits ($a_i$ or $b_j$) having value 1 or 0 is 1/2 (uniform distribution)} $\rightarrow$ In many cases in reality, this prior knowledge is unknown
\end{block}
\begin{block}{\textbf{Idea}}
 Minimax Approach \footnotemark[8] $\rightarrow$ Minimize the worst case scenario
 \[
 \min_{Design} \max_{Probability} Cost(Design, Probability)
 \]
\end{block}
\footnotetext[8]{\begin{tiny}Poor, H. Vincent. An introduction to signal detection and estimation. Springer Science \& Business Media, 1994. \end{tiny}}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Proposal}
\begin{block}{\textbf{Problems Statement}}
Each of PPs $a_i \cdot b_j$ is still regarded as a random variable with i.i.d. However, now the probability of input digits ($a_i$ or $b_j$) having value 1 is $\alpha$ $(0 \le \alpha \le 1)$ and $\alpha$ is unknown. The problem now is to find the optimal Correction Constant $C_M$ that minimize given type of errors with every $\alpha$. In other word, we need to solve the nested optimization problem:
\[
\min_{C_M} \max_{0 \le \alpha \le 1} E(C_M, \alpha)
\]  

in which, E is certain kind of the error measurement of the method
\end{block}

\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Minimax Expected Reduction Error}
\[
\min_{C_M} \max_{\alpha} E(C_M, \alpha) = \left|\mathbf{E}_{red} (C_M, \alpha)\right|
\]
in which, Expected Reduction Error $\mathbf{E}_{red} (C_M, \alpha)$:
\begin{small}
\begin{align*}
\mathbf{E}_{red} &= E \left\lbrace E_{red} (A, B) \right\rbrace \\
		&= E \left\lbrace (Z_{trunc} + C_M) - Z\right\rbrace\\
		&= C_M - E \left\lbrace (Z - Z_{trunc}) \right\rbrace\\
		&= C_M - E \left\lbrace \sum_{i+j = n+k+1}^{2n} (a_i\cdot b_j) \cdot 2^{-i-j} \right\rbrace\\
		&= C_M - \sum_{i+j = n+k+1}^{2n} E \left\lbrace (a_i\cdot b_j)\right\rbrace \cdot 2^{-i-j} \\
&= C_M - \frac{\alpha^2}{0.5^2}\cdot C_L ~~ \text{(\textit{Similar to Lim's method})}\\
&= C_M - 4 \alpha^2 \cdot C_L~~(C_L ~\textit{is Lim's Correction Value})\\
\end{align*}
\end{small}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Minimax Expected Reduction Error (cont.)}
\[
\min_{C_M} \max_{0 \le \alpha \le 1} E(C_M, \alpha) = \left| C_M - 4 \alpha^2 \cdot C_L \right|
\] 
\begin{columns}[c]
\column{0.65\textwidth}
\includegraphics[width=\columnwidth]{imgs/mnm_red.jpg} 
\column{0.35\textwidth}
\begin{small}
The optimal $C_M^*$ is 
\begin{align*}
C_M^* &= \frac{\max(4 \alpha^2 \cdot C_L) - \min(4 \alpha^2 \cdot C_L)}{2} \\
&= 2 \cdot C_L
\end{align*}
$\rightarrow$ The optimal $E(C_M, \alpha)$ is also $2\cdot C_L$

$\rightarrow$ With $C_M = C^*_M$, the smallest error happened when $\alpha = \sqrt{2}$
\end{small}
\end{columns}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Minimax Expected Total Error}
\[
\min_{C_M} \max_{\alpha} E(C_M, \alpha) = \left|\mathbf{E}_{total} (C_M, \alpha)\right|
\]
in which, the Expected Total Error $\mathbf{E}_{total}$
\[
\mathbf{E}_{total}(C, \alpha) = E\left\lbrace {(\frac{\left[2^n(Z_{trunc} + C)\right]}{2^n} - Z)} \right\rbrace
\]
\begin{itemize}
\item Rounding operation $\rightarrow$ can not reduce $\mathbf{E}_{total}$ to simple function
\item Numerical Method $\rightarrow$ Optimization Techniques
\end{itemize}
\end{frame}
\section{Conclusion and Future Work}
\subsection*{Conclusion and Future Work}
\begin{frame}
\frametitle{Conclusion and Future Work}
\begin{itemize}
\item Survey about state-of-the-art methods on Truncated Multipliers
\item Implemented in Matlab and Verilog code; synthesized designs on Xilinx Virtex-5 FPGA 
\item Proposed Minimax approach to deal with uncertainties of inputs and a preliminary results with Reduction Error
\item Future Work:
\begin{itemize}
\item Working on optimization techniques for Minimax Expected Total Error
\item Working on applying Minimax to Accurately Truncated Multipliers (Maximum Absolute Error $\le$ 1ulp)
\end{itemize}
\end{itemize}
\end{frame}
%------------------------------------------------

\appendix
\begin{frame}[allowframebreaks]
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{ma:1990}
G.~K. Ma and F.~J. Taylor.
\newblock Multiplier policies for digital signal processing.
\newblock {\em ASSP Magazine, IEEE}, 7(1):6--20, 1990.

\bibitem{lim:1992}
Y.~C. Lim.
\newblock Single-precision multiplier with reduced circuit complexity for
  signal processing applications.
\newblock {\em Computers, IEEE Transactions on}, 41(10):1333--1336, 1992.

\bibitem{schulte:1993}
M.~J. Schulte and E.~E. Swartzlander.
\newblock Truncated multiplication with correction constant [for dsp].
\newblock In {\em VLSI Signal Processing, VI, 1993., [Workshop on]}, pages
  388--396, 1993.

\bibitem{king:1997}
E.~J. King and E.~E. Swartzlander.
\newblock Data-dependent truncation scheme for parallel multipliers.
\newblock In {\em Signals, Systems \& Computers, 1997. Conference Record of the
  Thirty-First Asilomar Conference on}, volume~2, pages 1178--1182 vol.2, 1997.
\bibitem{stine:2003}
J.~E. Stine and O.~M. Duverne.
\newblock Variations on truncated multiplication.
\newblock In {\em Digital System Design, 2003. Proceedings. Euromicro Symposium
  on}, pages 112--119, 2003.
\bibitem{petra:2010}
N.~Petra, D.~De~Caro, V.~Garofalo, E.~Napoli, and A.~G.~M. Strollo.
\newblock Truncated binary multipliers with variable correction and minimum
  mean square error.
\newblock {\em Circuits and Systems I: Regular Papers, IEEE Transactions on},
  57(6):1312--1325, 2010.
\bibitem{tuan2014}
T.~Nguyen.
\newblock {\em Truncated Multipliers Version 1}, 2014.
\newblock Available at {http://trunc-mult-aio.googlecode.com/svn/trunk/}.
\bibitem{poor1994introduction}
H~Vincent Poor.
\newblock {\em An introduction to signal detection and estimation}.
\newblock Springer, 1994.

\end{thebibliography}
}

\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}
\Huge{\centerline{Thank You!}}
\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 